package com.app.sort;

import java.util.Arrays;

public class quickSort {

    public static void main(String[] args) {
        quickSort qs = new quickSort();
        int[] data = new int[]{4, 9, 88, 76, 54, 1, 4, 7, 0};
        System.out.println("sort before:" + Arrays.toString(data));
        qs.quick_sort(data, 0, data.length - 1);
        System.out.println("sort after:" + Arrays.toString(data));
    }


    public void quick_sort(int[] data, int start, int end) {

        final int o_start = start;
        final int o_end = end;
        int point = data[o_start];
        while (start < end) {
            while (start < end && data[end] > point) {
                end--;
            }
            while (start < end && data[start] <= point) {
                start++;
            }
            int tmp = data[start];
            data[start] = data[end];
            data[end] = tmp;
        }

        int tmp = data[start];
        data[start] = point;
        data[o_start] = tmp;


        if (o_start < start - 1) {
            quick_sort(data, o_start, start - 1);
        }
        if (end + 1 < o_end) {
            quick_sort(data, end + 1, o_end);
        }


    }
}

